package com.godme.sort;

import java.util.Arrays;

public class CountSort {


    public static int[] count(int[] arr){
        int[] store = new int[10];
        for (int value : arr) {
            store[value] += 1;
        }
        return store;
    }

    public static void combine(int[] countArray, int[] originArray, int sortIndex){
        if(sortIndex >= originArray.length){
            return;
        }
        int countCursor = 0;
        while(countArray[countCursor] <= 0){
            countCursor ++;
        }
        originArray[sortIndex] = countCursor;
        countArray[countCursor] --;
        combine(countArray, originArray, sortIndex+1);
    }

    public static void combine2(int[] countArray, int[] originArray){
        int sortIndex = 0;
        int countCursor = 0;
        while(sortIndex < originArray.length){
            while(countArray[countCursor] <= 0){
                countCursor ++;
            }
            originArray[sortIndex] = countCursor;
            sortIndex += 1;
            if(--countArray[countCursor] <= 0){
                countCursor ++;
            }
        }
    }

    public static void countSort(int[] arr){
//        combine(count(arr), arr, 0);
        combine2(count(arr), arr);
    }

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        countSort(arr);
        System.err.println(Arrays.toString(arr));
    }





}
